package dp;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: DELL
 * Date: 2023-09-20
 * Time: 7:22
 */
public class DP_Training {

    /**
     * 最长等差数列
     */
    public int longestArithSeqLength(int[] nums) {
        // 优化
        Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
        hash.put(nums[0], 0);

        // 建表
        int n = nums.length;

        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) // 初始化
            Arrays.fill(dp[i], 2);

        int ret = 2;
        for (int i = 1; i < n; i++) // 固定倒数第⼆个数
        {
            for (int j = i + 1; j < n; j++) // 枚举倒数第⼀个数
            {
                int a = 2 * nums[i] - nums[j];
                if (hash.containsKey(a)) {
                    dp[i][j] = dp[hash.get(a)][i] + 1;
                    ret = Math.max(ret, dp[i][j]);
                }
            }
            hash.put(nums[i], i);
        }
        return ret;
    }

    /**
     * 最长定差子序列
     */
    public int longestSubsequence(int[] arr, int difference) {
        // dp[i] 表示以 i 位置为结尾时的所有子序列中, 最长等差子序列的长度
        // 假设 arr数组为 {f,c,w,e, b, a}  以 a 为 i 位置结尾的所有子序列中, 如果 a 和 b 符合顶差子序列, 则定差子序列满足一个条件. b = a - differnce.
        // 状态转移推导 :
        // 当 i 位置自己成一个子序列是, 最长顶差子序列长度为 1
        // 当 i 位置(a)和 j 在[0, i - 1] 构成最长顶差子序列时, 其前一个元素已经是确定了. 就是 b. 那么就需要在 [0, i - 1] 中找值为 b 的所有情况都符合. 那么, 那个 b 构成的最长子序列长度更长呢 ?  应当为 [0, i - 1] 位置最后一个 b.
        // 比如这个数组 {...b, , b, b, ,a};
        // 那么, a 可以和前面三个 b 任意一个构成顶差子序列. 结果为 dp[j] + 1;
        // 三个 b 分别为 j1 j2 j3 这三个有什么区别. 在 dp 表中. dp[j3] >= dp[j2] >=dp[j3].  由于dp 中存的是以 i 位置为结尾的所有子序列中构成最长等差子序列的长度. 越往后, 三个 b 值相同, 他们的前一个等差数也是确定的. b 越往后, 意味着中间元素越多, 构成的最长等差子序列长度可能越长.
        // 因此我们只需要考虑最后一个位置的 b 即可.
        // 也就是 dp[i] = i 位置前符合等差数的最后一个位置的那个等差数 dp[j], 加上 1

        // 优化 :
        // 1. 如果将 b 也就是 i 位置这个数要找的等差数 + dp[j] 放到 hash.
        // 2. 如果将 a 也就是 i 位置对应元素 + dp[i] 和这个元素的最长定差序列长度放到 hash

        // 这样可以通过遍历, 从左往右可以将所有的 b 都进行添加到 hash 表中, 并且最后一个 b 会覆盖前面的所有 b 和他对应的 dp 值. 还可以省去 dp[0] = 1 的初始化.

        // hash 中键值对关系为 arr[i] : dp[i] 也就是每个位置的元素为结尾时对应的子序列中最长顶差子序列长度.
        Map<Integer, Integer> hash = new HashMap<>();
        int maxLen = 1;
        for (int a : arr) {
            // a - difference 也就是 b
            // 如果[0, i - 1] 中存在 a 前面的等差数 b. 那就是以这个数为结尾对应的最长顶差子序列的长度 + i 位置这个单独数构成新的最长顶差子序列.
            // 如果不存在. 那么只能 i 位置单独构成, 找不到 i 位置前一个固定的等差数 b. 最终最长顶差子序列长度为 1
            hash.put(a, hash.getOrDefault(a - difference, 0) + 1);
            // a 为遍历数组中每个元素.
            maxLen = Math.max(maxLen, hash.get(a));
        }

        // 确认返回值
        return maxLen;
    }
}
